package offerbook;

import utils.ListNode;
import utils.ListUtil;

import java.util.HashMap;
import java.util.Map;

/**
 * 拷贝普通单向链表
 * @date 2020/3/9 19:40
 */
public class Code26_CopyList1 {
    //方式一：1)直接拷贝,额外空间是O(1)
    public static ListNode copy(ListNode head) {
        if(head == null) return null;
        ListNode p1 = head;
        ListNode newNode = new ListNode(p1.val);
        ListNode p2 = newNode;
        while (p1.next != null){
            p1 = p1.next;
            p2.next = new ListNode(p1.val);
            p2 = p2.next;
        }
        return newNode;
    }
    //利用HashMap,额外O(n)空间,K是Node，V是Node的拷贝
    public static ListNode copy1(ListNode head){
        if(head == null) return null;
        ListNode p1 = head;
        Map<ListNode,ListNode> map = new HashMap<>();
        map.put(p1,new ListNode(p1.val));
        while (p1.next != null){
            p1 = p1.next;
            map.put(p1,new ListNode(p1.val));
        }
        //把value也就是拷贝节点连接起来
        p1 = head;
        ListNode newHead = map.get(p1);
        ListNode p2 = newHead;
        while (p1.next != null){
            p1 = p1.next;
            p2.next = map.get(p1);
            p2 = p2.next;
        }
        return newHead;

    }


    /**
     * 方式3：把拷贝的节点插入到当前节点的next，然后分离
     */
    public static ListNode copy2(ListNode head){
        if(head == null) return null;
        ListNode p = head;
        while (p != null){
            ListNode next = p.next;
            //拷贝p放入p.next
            p.next = new ListNode(p.val);
            //把拷贝的p.next与 next连接
            p.next.next = next;
            p = next;
        }
        //分离
        p = head;
        ListNode newHead= p.next;
        ListNode p2 = newHead;
        while (p != null){
            //拷贝的点
            ListNode copy = p.next;
            //下一个原来的点
            ListNode next = p.next.next;
            //连接拷贝的点
            p2.next = copy;
            p2 = p2.next;
            //连接原来的点
            p.next = next;
            p = next;
        }
        return newHead;

    }
    public static void main(String[] args) {
        ListNode head1 = new ListNode(7);
        head1.next = new ListNode(9);
        head1.next.next = new ListNode(1);
/*        head1.next.next.next = new ListNode(8);
        head1.next.next.next.next = new ListNode(5);
        head1.next.next.next.next.next = new ListNode(2);
        head1.next.next.next.next.next.next = new ListNode(5);*/
        ListUtil.printLinkedList(head1);
        ListNode copy = copy2(head1);
        ListUtil.printLinkedList(copy);
    }
}
